package graph;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;

public class DirectGraph extends Graph{

	/**
	 * *
	 * nữa bậc ngoài 
	 */
	public int outVertexLevel(int[][] matrix,int vertex){
		int temp=0;
			for(int i=0;i<matrix.length;i++){
				temp+=matrix[vertex][i];
		}
		return temp;
	}
	
	/**
	 * 
	 * nữa bậc trong
	 */
	public int inVertexLevel(int[][] matrix,int vertex){
		int temp=0;
			for(int i=0;i<matrix.length;i++){
				temp+=matrix[i][vertex];
		}
		return temp;
	}
	
	@Override
	public boolean innerGraph(int[][] matrix, int node) {
		return new UnDirectGraph().innerGraph(matrix, node) || new UnDirectGraph().innerGraph(moveDirectGraphToUnDirectGraph(matrix), node);
	}
	
	
	/**
	 * chuyển ma trận kề đồ thị có hướng thành vô hướng
	 * @param matrix
	 * @return
	 */
	private int[][] moveDirectGraphToUnDirectGraph(int[][] matrix){
		int[][] matrixUnDirectGraph = new int[matrix.length][matrix.length];
		int[] visitedVertex = new int[matrix.length];
		boolean checkReturn = false;
		while(true){
			checkReturn=true;
			int index=0;
			for(int i=0;i<visitedVertex.length;i++){
				if(visitedVertex[i]==0){
					checkReturn=false;
					index=i;
					break;
				}
			}
			if(checkReturn){
				break;
			}
			visitedVertex[index]++;
			int sum=0;
			for (int j = 0; j < matrix.length; j++) {
				if(j!=index){
					sum=matrix[index][j]+matrix[j][index];
					matrixUnDirectGraph[index][j]=sum;
					matrixUnDirectGraph[j][index]=sum;
				}else{
					matrixUnDirectGraph[index][index]=0;
				}
			}
		}
		return matrixUnDirectGraph;
	}
	
	/**
	 * kiểm tra nữa bậc trong bằng nữa bậc ngoài
	 * @param matrix
	 * @return
	 */
	private boolean checkoutVertexLevelEqualsInVertexLevel(int[][] matrix){
		for(int i=0;i<matrix.length;i++){
			if(outVertexLevel(matrix, i)!=inVertexLevel(matrix, i)){
				return false;
			}
		}
		return true;
	}
	
	
	@Override
	public boolean checkEuler(int[][] matrix, int node) {
		if(new UnDirectGraph().innerGraph(moveDirectGraphToUnDirectGraph(matrix), node) && checkoutVertexLevelEqualsInVertexLevel(matrix)){
			return true;
		}
		return false;
	}

	@Override
	public int innerGraphElement(int[][] matrix, int vertex,int element) {
		// TODO Auto-generated method stub
		return 0;
	}


	@Override
	public boolean checkTree(int[][] matrix) {
		// TODO Auto-generated method stub
		return false;
	}


	@Override
	public int countEdgeGraph(int[][] matrix) {
		int count = 0;
		for (int i = 0; i < matrix.length; i++) {
			for(int j=0;j<matrix.length;j++){
				count+=matrix[i][j];
			}
			for(int k=0;k<matrix.length;k++){
				count+=matrix[k][i];
			}
		}
		return count/2;
	}

	@Override
	public boolean checkPathBetweenTwoVertex(int[][] matrix, int u, int v) {
		if(u==v) return true;
		Stack<Integer> stack = new Stack<Integer>();
		int[] visitedVertex = new int[matrix.length];
		visitedVertex[u]++;
		stack.push(u);
		int vertex = u;
		boolean next = false;
		loops1: while (!stack.isEmpty()) {
			next = false;
			loops2: for (int i = 0; i < matrix.length; i++) {
				if (matrix[vertex][i] != 0 && visitedVertex[i] == 0) {
					visitedVertex[i]++;
					stack.push(i);
					vertex = i;
					next = true;
					if (i == v) {
						return true;
					}else{
						break loops2;
					}
				}
			}
			if (next == false) {
				boolean checkCrossAllVertex= true;
				for(int i=0;i<visitedVertex.length;i++){
					if(visitedVertex[i]!=1){
						checkCrossAllVertex = false;
					}
				}
				if(checkCrossAllVertex){
					return false;
				}else{
					vertex = stack.pop();
				}
			}
		}
		return false;
	}

	@Override
	public int countLevelOfVertex(int[][] matrix, int vertex) {
		return outVertexLevel(matrix, vertex)+inVertexLevel(matrix, vertex);
	}
	
	public static void main(String[] args) throws IOException {
		DirectGraph test = new DirectGraph();
		String path = "directedgraph.txt";
		//test.readFile(path);
		System.out.println((test.innerGraph(test.readFile(path), 0)));
		//System.out.println(test.checkPathBetweenTwoVertex(test.readFile(path), 3, 4));
	}

	@Override
	public void printAllPathBetweenTwoVertex(int[][] matrix, int u, int v) {
		if(!checkPathBetweenTwoVertex(matrix,u,v)){
			System.out.println("Khong co duong di");
		}
		System.out.println("Duong di la:");
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(u);
		List<Integer> checkAllVertexNext = new ArrayList<Integer>();
		for(int i=0;i<matrix.length;i++){
			if(matrix[u][i]!=0 && !stack.contains(i)){
				checkAllVertexNext.add(i);
			}
		}
		for(int i=0;i<checkAllVertexNext.size();i++){
			int temp = checkAllVertexNext.get(i);
			stack.push(temp);
			if(temp==v){
				printPath(stack);
			}else{
				printAllPathBetweenTwoVertex(matrix,temp,v,stack);
			}
			stack.pop();
		}
		
	}

	private void printAllPathBetweenTwoVertex(int[][] matrix, int u, int v,
			Stack<Integer> stack) {
		List<Integer> checkAllVertexNext = new ArrayList<Integer>();
		for(int i=0;i<matrix.length;i++){
			if(matrix[u][i]!=0 && !stack.contains(i)){
				checkAllVertexNext.add(i);
			}
		}
		for(int i=0;i<checkAllVertexNext.size();i++){
			int temp = checkAllVertexNext.get(i);
			stack.push(temp);
			if(temp==v){
				printPath(stack);
			}else{
				printAllPathBetweenTwoVertex(matrix,temp,v,stack);
			}
			stack.pop();
		}
		
		
	}

	private void printPath(Stack<Integer> stack) {
		for(int i=0;i<stack.size();i++){
			System.out.print(stack.get(i)+" ");
		}
		System.out.println();
	}
}
